﻿#include "../include/BTreeClass.h"
#include <corecrt_malloc.h>
#include <vcruntime_string.h>

BTreeClass::BTreeClass()
{
	this->root = this->createNewNode();
}

BTreeClass::~BTreeClass()
{
	this->destroy(this->root);
}

void BTreeClass::insert(int value)
{
	if (!this->root)
	{
		return;
	}

	// 节点元素未满
	if (this->root->keyNum != ELEMENT_NUM)
	{
		this->insertNonFull(this->root, value);

		return;
	}

	// 节点元素已满 分裂节点

	this->root->leaf = false;

	this->splitBTreeLeaf(this->root, this->root, 0);

	this->insertNonFull(this->root, value);

}

BStruct* BTreeClass::createNewNode(int index, int key, size_t num)
{
	BStruct* node = (BStruct*)malloc(sizeof(BStruct));

	if (!node)
	{
		return nullptr;
	}

	node->keyNum = num;

	for (size_t i = 0; i < ELEMENT_NUM; i++)
	{
		node->keyData[i] = 0;
	}

	for (size_t i = 0; i < CHILD_NUM; i++)
	{
		node->childPtr[i] = nullptr;
	}

	node->keyData[index] = key;

	node->leaf = true;

	return node;
}

void BTreeClass::insertNonFull(BStruct* node, int value)
{
	size_t pos = node->keyNum;

	// 当前是叶子节点
	if (true == node->leaf)
	{
		this->addElementByCondition(node, value);
	}
	else
	{
		// 确定哪个分支
		while (0 < pos && value < node->keyData[pos - 1])
		{
			pos -= 1;
		}

		// 当前节点元素是否已满
		if (node->childPtr[pos]->keyNum == ELEMENT_NUM)
		{
			// 分裂
			this->splitBTreeLeaf(node, node->childPtr[pos], pos);

			if (value > node->keyData[pos])
			{
				pos += 1;
			}

		}
		// 向下寻找
		this->insertNonFull(node->childPtr[pos], value);
	}

}

void BTreeClass::splitBTreeLeaf(BStruct* parent, BStruct* node, size_t pos)
{

	if (nullptr == parent->childPtr[0])
	{
		this->noBranchByInsert(node);

		return;
	}

	/////////////////////////////////////////////////////////////////////////


	if (parent->keyNum == ELEMENT_NUM)
	{
		this->nodeGrowByInsert(node, parent);
		return;
	}

	this->nodeBifurcation(parent, node, pos);

}

void BTreeClass::destroy(BStruct* node)
{
	if (node)
	{
		for (size_t i = 0; i < node->keyNum; i++)
		{
			this->destroy(node->childPtr[i]);
		}

		free(node);
	}

	node = nullptr;
}

FindResult* const BTreeClass::findNode(int key)
{
	return this->auxiliaryByFind(this->root, key);
}



void BTreeClass::addElementByCondition(BStruct* node, int value) const
{
	size_t pos = node->keyNum;

	// 找到插入的位置 【按顺序排列】|1|3
	// 例如当前元素1|3 插入2 要保持顺序 则 要调换位置 1|2|3
	while (0 < pos && value < node->keyData[pos - 1])
	{
		// 调换顺序 保证从小到大排序
		node->keyData[pos] = node->keyData[pos - 1];

		pos -= 1;
	}

	node->keyData[pos] = value;

	node->keyNum += 1;
}

void BTreeClass::noBranchByInsert(BStruct* node)
{
	// 没有分支节点时
	size_t middleKey = node->keyData[MIDDLE_INDEX];

	BStruct* leftNode = this->createNewNode();

	size_t i = 0;

	for (i; i < MIDDLE_INDEX; i++)
	{
		leftNode->keyData[i] = node->keyData[i];
		leftNode->keyNum += 1;
	}

	node->childPtr[0] = leftNode;

	BStruct* rightNode = this->createNewNode();

	size_t j = 0;

	for (i = MIDDLE_INDEX + 1; i < ELEMENT_NUM; i++)
	{
		rightNode->keyData[j] = node->keyData[i];
		rightNode->keyNum += 1;

		j++;
	}

	node->childPtr[1] = rightNode;

	this->keepTheMiddleNode(node);

	// 将中间节点 放在第一个位置，
	node->keyData[0] = this->root->keyData[MIDDLE_INDEX];

	node->keyData[MIDDLE_INDEX] = 0;

	node->keyNum = 1;

	node->leaf = false;
}

void BTreeClass::nodeGrowByInsert(BStruct* parent, BStruct* node)
{
	size_t i = 0;

	size_t moldTakingNumber = ELEMENT_NUM - 1;

	BStruct* branchLeft = this->createNewNode();

	branchLeft->leaf = false;

	for (i = 0; i <= MIDDLE_INDEX; i++)
	{
		if (i < MIDDLE_INDEX)
		{
			branchLeft->keyData[i] = parent->keyData[i];

			parent->keyData[i] = '\0';

			parent->keyNum -= 1;

			branchLeft->keyNum += 1;
		}

		branchLeft->childPtr[i] = parent->childPtr[i];

		parent->childPtr[i] = nullptr;
	}

	BStruct* branchRight = this->createNewNode();

	branchRight->leaf = false;

	size_t j = 0;

	for (i = MIDDLE_INDEX + 1; i < CHILD_NUM; i++)
	{
		if (i < ELEMENT_NUM)
		{
			branchRight->keyData[j] = parent->keyData[i];

			parent->keyData[i] = '\0';

			parent->keyNum -= 1;

			branchRight->keyNum += 1;
		}

		branchRight->childPtr[j] = parent->childPtr[i];


		parent->childPtr[i] = nullptr;

		j++;
	}

	// 留下中间节点
	this->keepTheMiddleNode(node);

	// 将中间节点 放在第一个位置，
	parent->keyData[0] = parent->keyData[MIDDLE_INDEX];

	parent->keyData[MIDDLE_INDEX] = '\0';

	parent->keyNum = 1;

	parent->childPtr[0] = branchLeft;

	parent->childPtr[1] = branchRight;
}

void BTreeClass::nodeBifurcation(BStruct* parent, BStruct* node, size_t pos)
{
	size_t middleKey = node->keyData[MIDDLE_INDEX];

	this->addElementByCondition(parent, middleKey);

	size_t next = MIDDLE_INDEX + 1;

	size_t i = 0;

	for (i = MIDDLE_INDEX; i < ELEMENT_NUM - 1; i++)
	{
		node->keyData[i] = node->keyData[i + 1];
	}


	node->keyData[i] = '\0';

	node->keyNum -= 1;

	BStruct* rightNode = this->createNewNode();

	size_t index = 0;

	for (i = MIDDLE_INDEX; i < CHILD_NUM - 1; i++)
	{
		if (i < ELEMENT_NUM - 1)
		{
			rightNode->keyData[index] = node->keyData[i];

			rightNode->keyNum += 1;

			node->keyData[i] = '\0';

			node->keyNum -= 1;
		}

		rightNode->childPtr[index] = node->childPtr[i + 1];

		node->childPtr[i + 1] = nullptr;

		index += 1;
	}

	rightNode->leaf = node->leaf;

	// 确定插入那个分支，如果元素填满则有元素+1个分支！！！
	// 分支满 则要增加树的高度
	parent->childPtr[pos + 1] = rightNode;

	node->keyData[MIDDLE_INDEX] = '\0';

}

void BTreeClass::keepTheMiddleNode(BStruct* node)
{
	size_t i = 0;
	// 留下中间节点
	while (i < ELEMENT_NUM)
	{
		if (i != MIDDLE_INDEX) {
			node->keyData[i] = '\0';
		}
		i++;
	}
}

FindResult* BTreeClass::auxiliaryByFind(BStruct* node, int key)
{
	BStruct* parent = nullptr;

	int branchIndex = 0;

	size_t pos = 0;

	// key所在node元素中的位置
	int keyPos = 0;

	// 结果集
	FindResult* res = nullptr;

	while (node)
	{
		pos = this->getPos(node, key);

		keyPos = pos - 1;

		if (0 > keyPos)
		{
			// 获取key下标
			keyPos = 0;
		}

		if (key == node->keyData[keyPos])
		{
			res = (FindResult*)malloc(sizeof(FindResult));

			if (!res)
			{
				return nullptr;
			}

			res->node = node;

			res->parent = parent;

			res->pos = keyPos;

			res->branchPos = branchIndex;

			return res;
		}

		parent = node;

		branchIndex = pos;

		node = node->childPtr[pos];
	}

	return res;
}

unsigned int BTreeClass::getPos(BStruct* node, int value)
{
	size_t pos = node->keyNum;
	// 找到插入的位置 【按顺序排列】|1|3
	// 例如当前元素1|3 插入2 要保持顺序 则 要调换位置 1|2|3
	while (0 < pos && value < node->keyData[pos - 1])
	{
		// 调换顺序 保证从小到大排序
		pos -= 1;
	}

	return pos;
}

int BTreeClass::pareseRightDateBySturct(BStruct* node)
{
	int data = node->keyData[node->keyNum - 1];

	node->keyData[node->keyNum - 1] = '\0';

	node->keyNum -= 1;

	return data;
}

int BTreeClass::pareseLeftDateBySturct(BStruct* node)
{

	int data = node->keyData[0];

	size_t moveForward = ELEMENT_NUM - 1;

	size_t first = 0;

	node->keyData[0] = '\0';

	for (size_t i = 0; i < moveForward; i++) {
		node->keyData[i] = node->keyData[i + 1];
	}

	node->keyNum -= 1;

	node->keyData[moveForward] = '\0';

	return data;
}

/*
	if (!res->parent)
	{
		BStruct* node = res->node;

		BStruct* left = node->childPtr[0];

		if (!left)
		{
			this->delNonFull(res);
			return;
		}

		BStruct* right = node->childPtr[1];

		return;
	}*/
void BTreeClass::delKey(int key)
{
	FindResult* const res = this->findNode(key);

	if (!res)
	{
		free(res);
		return;
	}

	this->delNonFull(res);

	free(res);
}

void BTreeClass::delNonFull(FindResult* res)
{
	BStruct* node = res->node;

	size_t pos = res->pos;

	int key = node->keyData[pos];

	BStruct* siblings = res->parent->childPtr[res->branchPos + 1];

	if (MINIMUM_NUMBER_OF_ELEMENTS >= node->keyNum)
	{
		// 节点不丰满

		if (MINIMUM_NUMBER_OF_ELEMENTS < siblings->keyNum)
		{
			// 兄弟节点丰满
			// 节点向父节点要了一个key
			size_t parentKeyPos = this->getPos(res->parent, key);

			node->keyData[pos] = res->parent->keyData[parentKeyPos];

			// 兄弟节点的最左边的key 被提拔上去了
			size_t promotionKeyPos = this->getPos(siblings, key);

			res->parent->keyData[parentKeyPos] = siblings->keyData[promotionKeyPos];

			this->deleteElementandMoveForward(siblings, parentKeyPos);
		}
		else
		{
			// 都不丰满
			this->merge(res);
		}

	}
	else
	{
		// 节点丰满
		// 直接干掉
		this->deleteElementandMoveForward(node, pos);
	}

}

void BTreeClass::deleteElementandMoveForward(BStruct* node, unsigned int pos)
{
	node->keyData[pos] = '\0';
	for (size_t i = pos; i < ELEMENT_NUM - 1; i++)
	{
		node->keyData[i] = node->keyData[i + 1];
	}

	node->keyNum -= 1;

	node->keyData[node->keyNum] = '\0';
}

void BTreeClass::merge(FindResult* data)
{
	BStruct* sibling = data->parent->childPtr[data->branchPos + 1];

	BStruct* node = data->node;

	size_t j = 0;

	for (size_t i = MIDDLE_INDEX + 1; i < ELEMENT_NUM; i++)
	{
		node->keyData[i] = sibling->keyData[j];

		/*if (i + 1 <= ELEMENT_NUM)
		{
			data->parent->childPtr[i] = data->parent->childPtr[i + 1];
		}*/

		node->keyNum += 1;

		j++;
	}

	if (!sibling->childPtr[0])
	{
		free(sibling);

		sibling = nullptr;

		for (size_t i = data->branchPos + 1; i < MAX_NUM - 1; i++)
		{
			data->parent->childPtr[i] = data->parent->childPtr[i + 1];
		}

		data->parent->childPtr[MAX_NUM - 1] = nullptr;
	}

	// 向父节点要一个
	size_t pos = this->getPos(data->parent, node->keyData[data->pos]);

	node->keyData[MIDDLE_INDEX] = data->parent->keyData[pos];

	node->keyNum += 1;

	this->deleteElementandMoveForward(data->parent, pos);

	this->deleteElementandMoveForward(node, data->pos);
}
